package Graph.TopoSort;

import java.util.LinkedList;

public class Kahn {
    private int v;
    private LinkedList<Integer> adj[];
    boolean found = false;

    public Kahn(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }

    public void topoSortByKahn() {
        //统计每个节点的入度
        int[] inDegree = new int[v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                //i->w
                int w = adj[i].get(j);
                inDegree[w]++;
            }
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < v; i++) {
            //inDegree[i]==0说明这个顶点的入度为0
            //那就可以把它们先放进队列，等下先执行它们
            if (inDegree[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            //队头元素出队
            int i = queue.remove();
            System.out.println("->" + i);
            for (int j = 0; j < adj[i].size(); j++) {
                int k = adj[i].get(j);
                //依赖i的元素的入度减1
                inDegree[k]--;
                //如果入度为0，说明它可以被执行了，就先加入队列等待被执行
                if (inDegree[k] == 0) queue.add(k);
            }
        }
    }
}
